Feature #7: Maximum Users

Implement the "Maximum Number of Users" feature for our "Cellular Operator AT&T" project.

We'll cover the following

Description
Solution
Complexity measures
- Time complexity
- Space complexity

Description#

On a busy intersection with heavy vehicular and pedestrian traffic, the operator deploys a base station. The number of users connected to that base station keeps changing rapidly, as people enter and leave its coverage area. The base station quickly dumps the current number of users to a list every 1 ms.

The operator wants to analyze the data to improve coverage for its users. However, the data contains rapid variations that don’t carry useful information from a network management perspective. To deal with the variation, the operator wants to find the maximum number of users connected to the base station in every k ms sliding window.

Given a list of values, we need to create a sliding window of size k (shown in red) and find the max in each sliding window. Different sliding windows in the given list are shown in separate rows in the following illustration, along with the maximum value in the sliding window.

Solution#

Here, we will find the maximum number of users who are connected to the base station in the selected k millisecond windows. Each entry in the array will show the number of users who are connected to the base station in the 1 ms window.

Here is how we will implement this feature:

We are given an array of integers.
If the value at the current index is less than the value at the previous index of the array or all the value(s) of the index(es) in mqueue, then we will push the current index to the mqueue. Otherwise, we will perform the pop operation.
During the Enum.reduce execution, if the mqueue value (index) at zero index is equal to the i-k, then we will perform the remove_left operation in the mqueue.
If the index of the given array is greater than or equal to the window slide length (k), then we will push the maximum value of the mqueue to the result array.

This way, the result array will contain the maximum number for each window slide (k).

The following illustrations show us how the solution given above will work:

Obtain maximum users using monotonic queue

1 of 28

Obtain maximum users using monotonic queue

2 of 28

Obtain maximum users using monotonic queue

3 of 28

Obtain maximum users using monotonic queue

4 of 28

Obtain maximum users using monotonic queue

5 of 28

Obtain maximum users using monotonic queue

6 of 28

Obtain maximum users using monotonic queue

7 of 28

Obtain maximum users using monotonic queue

8 of 28

Obtain maximum users using monotonic queue

9 of 28

Obtain maximum users using monotonic queue

10 of 28

Obtain maximum users using monotonic queue

11 of 28

Obtain maximum users using monotonic queue

12 of 28

Obtain maximum users using monotonic queue

13 of 28

Obtain maximum users using monotonic queue

14 of 28

Obtain maximum users using monotonic queue

15 of 28

Obtain maximum users using monotonic queue

16 of 28

Obtain maximum users using monotonic queue

17 of 28

Obtain maximum users using monotonic queue

18 of 28

Obtain maximum users using monotonic queue

19 of 28

Obtain maximum users using monotonic queue

20 of 28

Obtain maximum users using monotonic queue

21 of 28

Obtain maximum users using monotonic queue

22 of 28

Obtain maximum users using monotonic queue

23 of 28

Obtain maximum users using monotonic queue

24 of 28

Obtain maximum users using monotonic queue

25 of 28

Obtain maximum users using monotonic queue

26 of 28

Obtain maximum users using monotonic queue

27 of 28

Obtain maximum users using monotonic queue

28 of 28

defmodule Solution do
    alias Okasaki.Deque, as: Deque
    def max_users(array, size, k) do
        mqueue = Deque.new([]) # Store given array indices. 
        result = [] # Store maximum value of every window slide.
        0..size-1
        |> Enum.reduce({result, mqueue}, fn(i, {result, mqueue}) ->
            mqueue = 
                array
                |> update_mqueue(mqueue, i) 
                |> Deque.insert_right(i)
            # Remove first element if it's outside the window slide.
            {:ok, {first, mqueue_rest}} = Deque.remove_left(mqueue)
            mqueue = if first == i - k, do: mqueue_rest, else: mqueue
            # If given array index greater than and equal to the window slide size, then push the maximum value in result array.
            {:ok, {first, _}} = Deque.remove_left(mqueue)
            result = if i >= k - 1, do: [array[first] | result], else: result
            {result, mqueue}
        end)
        |> elem(0)
        |> :lists.reverse
    end
    def update_mqueue(array, mqueue, i) do        
        cond do
            Deque.size(mqueue) > 0 ->

Enter to Rename, Shift+Enter to Preview

Maximum users

Complexity measures#

Time complexity	Space complexity
$O(n)$	$O(k)$

Time complexity#

Here, we are iterating the outer Enum.reduce function n times and calling the inner recursion function, update_mqueue, k times. Here, n is the size of the given array, and k is the size of the sliding window, which is constant. Therefore, the time complexity will be $O(n)$ .

Space complexity#

The space complexity will be $O(k)$ , because we need to store a maximum of k values in the mqueue.

Feature #6: Densest Deployment

Feature #8: Maximum Signal Strength